package 链表;

import java.util.*;

public class No234回文链表 {

    /**
     * 请判断一个链表是否为回文链表。
     *
     * 示例 1:
     * 输入: 1->2
     * 输出: false
     *
     * 示例 2:
     * 输入: 1->2->2->1
     * 输出: true
     * 进阶：
     * 你能否用 O(1) 空间复杂度解决此题？
     */

    //方法一:集合方法  空间为n
    public static boolean isPalindrome(ListNode head) {

        if(head==null||head.next==null)
            return true;

        List<Integer> list=new ArrayList<>();

        while (head!=null){
            list.add(head.val);
            head=head.next;
        }

        int left=0;
        int right=list.size()-1;
        if(list.size()%2==0){
            //偶数个
            while (left-1!=right){
                if(!list.get(left++).equals(list.get(right--)))
                    return false;
            }
        }else{
            //奇数个
            while (left!=right){
                if(!list.get(left++).equals(list.get(right--)))
                    return false;
            }
        }

        return true;
    }

    static ListNode cur=null;
    //方法二:递归方法 空间为n
    public static boolean isPalindromeDG(ListNode head) {
        /**
         * 1.父函数吃什么?(包含return什么,return上去的怎么处理?)
         * 父函数吃子函数返回的boolean
         * 2.根据题意如何递归前,递归后如何操作
         * 递归到最后一个,然后和第一个比较
         */
        if(head==null||head.next==null)
            return true;
        cur=head;
        return dg(head);
    }

    public static boolean dg(ListNode listNode){

        boolean flag = dg(listNode.next);
        if(!flag)
            return false;

//        System.out.print(listNode.val);

        if(cur.val!=listNode.val) {
            cur=cur.next;
            return false;
        }
        else {
            cur=cur.next;
            return true;
        }
    }

    //空间为1
    //方法三:快慢指针遍历到中间节点时,让后一半链表进行翻转,然后再来比较
    //获取中间节点是slow无next,让后半段总是多于等于前半段
    public static boolean isPalindromeGood(ListNode head){

        if(head==null||head.next==null)
            return true;

        ListNode midNode=getMidNode(head);
        ListNode backHalf=midNode.next;
        midNode.next=null;
        ListNode backFast = reversal(backHalf);

        boolean flag=true;
        //不一定一半n
        while (head!=null&&flag){
            flag=backFast.val==head.val;
            head=head.next;
            backFast=backFast.next;
        }
        return flag;

    }

    //反转链表方法
    private static ListNode reversal(ListNode head){

        ListNode next;
        ListNode op=null;
        ListNode cur=head;

        //1->2->3->4->5
        while (cur!=null){

            next=cur.next;

            cur.next=op;

            op=cur;

            cur=next;
        }

        return op;
    }

    //找中间节点方法
    private static ListNode getMidNode(ListNode head){

        ListNode slow=head;
        ListNode fast=head.next.next;

        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,5,3,2,1};
        ListNode listNode = ListNode.createListNode(arr);
        boolean palindromeDG = isPalindromeGood(listNode);
        System.out.println(palindromeDG);
    }

}
